1. Field of the Invention
The present invention relates to an apparatus, a method, and a computer program product for processing database that are used for processing structured documents having a hierarchical structure.
2. Description of the Related Art
In recent years, databases (e.g., XML databases) that store structured documents therein have become more prevalent, due to the growing popularity of structured documents like XML documents. As an example of languages that can be used for making queries to such databases, XQuery has been proposed.
XQuery is a function-type language that can be used for making XML queries and is characterized by having a FLWR syntax. The FLWR syntax denotes a syntax that includes a FOR clause, a LET clause, a WHERE clause, and a RETURN clause. An example of processes using XQuery is described in M. Fernandez, J. Simeon, B. Choi, A. Marian, G. Sur, Implementing XQuery 1.0: The Galax Experience, VLDB 2003.
In a FLWR syntax in XQuery, the FOR clause binds the items within a sequence to a variable. On the other hand, the LET clause binds the entire sequence to a variable. By combining the FOR clause and the LET clause, it is possible to make an advanced query that is suitable for XML. (It is not possible to express XML restructuring and aggregation without LET clauses.)
In XQuery, by using a LET clause, it is also possible to call a query having a nested structure in which a plurality of FOR clauses are used.
In database products that are currently available, LET clauses are often implemented so as to be compliant with a processing system for function-type languages. In the case where the implementation is in compliant with the processing system for function-type languages, when a query is made to a nested structure as described above, it is considered that there is an input output relationship between the outer XQuery data and the inner XQuery data in the nested structure. Thus, when the process on the outer XQuery data has been finished, each of the results of the process is forwarded, as a variable, to the inner XQuery data so that the inner XQuery data can be processed.
To make an advance query using XQuery, a nested structure as explained above is indispensable; however, a problem arises where, in the case where the implementation is in compliant with the processing system for function-type languages, the amount of calculation required by a nested structure having double or more nesting is large.
More specifically, because the processing system for function-type languages processes the inner portion after having processed the multiple loops in the outer portion, the process for the inner XQuery data is called as many times as the number of loops in the multiple loops. As a result, even if the number of nesting in the nested structure increases only by one, the amount of calculation increases by a huge amount.